\documentclass[11pt, journal]{IEEEtran}
\usepackage{amsmath, amsthm, amssymb}
\usepackage{graphicx}
\title{ProHash: A Protein-Protein Interaction Network Motif Discovery Tool}
\author{Robert~Kirchgessner,~\IEEEmembership{Graduate Student} Carlo~Pascoe,~\IEEEmembership{Graduate Student}}

\begin{document}

\maketitle

\begin{abstract}
Recent work in the analysis of biological networks have identified repeated functional modules, known as motifs, with biological and evolutionary significance. Motifs are present in various kinds of biological data, including gene sequences, metabolic networks, synaptic connection graphs, ecological systems, and protein-protein interaction networks. Motif detection in PPI networks is an NP-complete problem prompting previous solutions such as the methods used in Berg et. al. \cite {_lassig} or those in Shen et. al. \cite{Milo25102002} to utilize heuristics rather than an optimal approach. In this Project, we intend to design our own heuristic for the identification of motifs in protein-protein interaction networks by utilizing the novel application of feature-based indexing to the problem. Though feature-based indexing is commonly applied to such problems as multimedia fingerprinting and pattern recognition, it has yet to be applied to motif detection in PPI networks, where the large data sets are both spatially and computationally limiting. Our proposed method is evaluated by performing the same experiments as similar motif detection applications then comparing the obtained results for similarity and quality of detected motifs.
\end{abstract}

\section{Introduction}
Analyses of biological data such as protein-protein interaction networks, metabolic networks, gene expression networks, or phylogenetic trees reveal recurring patterns thought to be biologically significant. These patterns, known as motifs, are sub-graphs which appear more frequently in an input than in random graphs \cite{_survey}. The hope is by finding and classifying motifs it is possible to better understand the fundamental functionality of more complex biological structures. Detecting these motifs is an NP-complete problem and as such detection methods rely on heuristics which sacrifice some accuracy for speed.

Motif detection in protein-protein interaction (PPI) networks has uncovered interesting features in terms of repeated modules with biological and evolutionary significance \cite{Ciriello}. These modules can be considered as the fundamental building blocks of complex PPI networks \cite{Milo25102002} and therefore warrant investigation. In this paper, we present a new heuristic, ProHash, for the identification of motifs in protein-protein interaction networks which utilizes the novel application of feature-based indexing to the problem. Though feature-based indexing is commonly applied to many other problems such as multimedia fingerprinting and pattern recognition, it has yet to be applied to motif detection in PPI networks, where the large data sets are both spatially and computationally limiting. 

In order to detect motifs in PPI networks, ProHash will identify a set of features which can be used to represent regions of significance in an input network and once these features have been identified, a hashing function is used to generate a characteristic fingerprint for these regions of the network. By storing these fingerprints in a hash tree database, motifs can be identified quickly and easily through a quantitative comparison between database entries which reduces computation when searching for large motifs. 

 
\begin{figure*}[!ht] 
\begin{center}
\includegraphics{fig0.png}
\end{center}
 \caption{Example of the graph overlay generation using the random priority method a) Original input graph b) Generated overlay }
\end{figure*}

\section{Overview}
ProHash is a tool developed to identify motifs in PPI networks. ProHash utilizes a novel approach of applying a hashing function to reduce the time complexity of motif searches. The algorithm works by breaking down an input graph into a series of smaller sub-graphs, which are then hashed in order to generate a hash-graph. The hash-graph is a simplified form of an input graph which can be used in a variety of fasions to identify motifs, including two primary applications outlined in this paper: \emph{templated motif search}, and \emph{auto-aligned motif search}. Although ProHash was designed to work primarily on PPI network data, it supports any undirected graph dataset.

To determine the performance of the ProHash algorithm, it was run for motifs of different sizes with varying feature sizes for the organism \emph{S. cerevisiae} . The results were then compared against the output of the Kavosh algorithm \cite{kavosh}.

\section{Materials and Methods}
\subsection{Databases}
Protein-protein interaction data for \emph{S. cerevisiae} was taken from two sources: the MINT database (http://mint.bio.uniroma2.it/mint/) and MIPS database (http://www.helmholtz-muenchen.de/en/ibis). The data was downloaded in PSI-25 XML format. In order to utilize the data in ProHash, it was first pre-processed using Python scripts to convert the XML format into an edge-list format for easier processing.

\subsection{Hash-graph generation}
Before motifs can be detected, a hash-graph representation of the input network must first be calculated. Once the input graph is loaded into a linked-list graph structure, the calculation of the hash-graph is performed in three steps:

\begin{enumerate}
\item Graph overlay calculation using several methods 
\item Hash-graph generation from overlay
\item Calculation of sub-graph flux and hash-storage
\end{enumerate}

The graph overlay paritions an input graph into a set of sub-graphs of size 1...K, where K is the feature size. The feature size is the maximum number of vertices that should be partitioned into a sub-graph. When an overlay is performed, ProHash attempts to group sets of vertices into connected sub-graphs of size 1...K, with perference given to constructing larger sub-graphs. ProHash currently supports several methods of overlay generation, since an optimal solution of partitioning the graph is not known. Many of the methods give priority to high-degree vertices, since higher degree vertices appear more often as parts of graph motifs \cite{PhysRevE.71.016110}. The methods currently supported by ProHash are:

\subsubsection {Degree Priority}
A greedy method which generates connected subgraphs by selecting the highest degree adjacent vertices. Ties are broken using random selection.

\subsubsection {Random with Priority}
A random-walk method which selects the first vertex of the sub-graph by giving priority to the vertices with the highest priority in the graph. Subsequent vertices are selected by performing a random tranversal around the initial vertex.

\subsubsection {Random}
A random-walk method which ignores node degree. It selects an initial random vertex. Subsequent vertices are selected by performing a random traversal around the initial vertex.

An example graph overlay generated using the random priority method is shown in Fig 1.

Once the overlay is generated, the sub-graphs are converted into hashes. The edges between the hash nodes are weighted by the total number of edges between the two sub-graphs. The resulting hash-graph reduces the size of the original input graph, while maintaining information about specific patterns which occur in the graph. The current hash function  is as follows:

\begin{figure*}[ht] 
\begin{center}
\includegraphics[scale=0.45]{fig1.png}
\end{center}
\caption{Alignment between a candidate motif and the input graph with a score of 0.50 }
\end{figure*}

\begin{center}
\begin{equation}
h(s_{1})=\left \{ d(v_{1}), d(v_{2}), ... ,d(v_{n}) \right \} 
\label{hash}
\end{equation}
\begin{equation}
d(v_{1}) \geq  d(v_{2})  \geq ... \geq  d(v_{n})
\label{ordering}
\end{equation}
\end{center}

\subsection {Template motif alignment and detection}

Given a llst of candidate motifs, it is our goal to identify regions in the input graph where the candidate motifs occur. Each motif is categorized by a list of subgraph hashes and an overlay with connectivity and flux information in the same way as the hashed input graph. Given the hashed input graph G = (V,E) and hashed motif graph G' = (V,E), where each vertex is associated with a subgraph hash hi and each edge is associated with an edge weight fij equal to the flux between subgraphs, Our motif alignment strategy is as follows:

\begin{figure*}[ht]
\begin{equation*}
score = {min_{(x,y)\epsilon G.E}}\left \{\sum_{(i,j)\epsilon G'.E} \frac{|{f_{xy}} - {f'_{ij}}| + hashdiff({h_{x}}, {h'_{i}}) + hashdiff({h_{y}}, {h'_{j}})} {|G'.E|}  \right \}
\label{score}
\tag{5}
\end{equation*}
\end{figure*}

The method attempts to align each edge in the candidate motif to an edge in the main graph. incentive is given to vertices of the aligned  edge with similar hash value and to aligned edges with similar flux. Alignmed edges with the same flux value and vertices with the same hash valuses will produce a score of 0. The partial scores generated for each edge are normalized by a factor equal to the total number of edges in the candidate motif so that the total score generated for a motif with N1 hashes will be comparable to the total score generated for one with N2 hashes. Since we do not necessarily want to impose the strict condition that each alignment be an exact match, a threshold score value is used as a parameter to tweak output quality; for a given threshold and candidate motif, a list of alignmnet with score less than the threshold is returned and represents the number of occurances of the candidate motif in the input graph.An example alignment is shown in Fig 2. 


\subsection {Auto-aligned motif detection}
Unlike the template-based motif detection method, auto-aligned motif detection utilizes a direct comparison between sub-graph hashes within the generated hash-graph. It compares regions of the graph against itself in order to determine similar patterns that occur throughout the graph. The algorithm is as follows:

\begin{enumerate}

\item Build a scoring matrix for all sub-graphs 
\begin{equation}
{a_{ij}} = {a_{ji}} = |h(s_{i}) - h(s_{j})|
\label{score_mat}
\end{equation}

\item For each sub-graph row in the upper-triangle of the scoring matrix, find all similar sub-graphs 
\begin{equation}
similar({s_{i}},s_{j}) \rightarrow {a_{ij}} < Threshold
\label{simscore}
\end{equation}

\item Find a consensus pattern for all similar sub-graphs by adding their adjacency matrices and scaling by the total number of similar sub-graphs

\end{enumerate}

Each consensus pattern found in this manner is treated as a motif. Along with the actual pattern found, the number of occurences of that pattern is stored in a list for Z-score calculation. Note that it is possible that two disimilar sets of similar sub-graphs will produce the same consensus pattern, so it is necessary to check for graph isomorphisms with existing patterns before adding a new motif pattern to the list.

\begin{figure*}[ht] 
\begin{center}
\includegraphics{auto_feature10.png}
\end{center}
 \caption{Top scoring motifs for auto- aligned motif detection method for feature sizes of 10 vertices using MINT-DB PPI data for yeast}
\end{figure*}

\section{Results}
In order to compare the auto-aligned motif detection with Kavosh, we need to specify a large enough feature size to detect a variable size set of motifs. In Kavosh, the user can specify a specific motif size, allowing Kavosh to search specifically for a set of non-isomorphic motifs of a certain size (similar to ProHash's template search method.) The auto-aligned method, however, will pull out patterns up to the specified feature size, based on the similar features of the regions of the graph being compared. This will allow all patterns up to a specific size to be found if they occur frequently enough. The down side to this, however, is that small sub-graph partitions will be reported as having incorrectly high Z-scores.

The auto-aligned method was executed on the yeast PPI network dataset (~1000 vertices) from the MINT database. The feature size was set to 10, so motifs from 1 to 10 nodes could be found. The motif threshold for this method was set to one. The motifs found were compared against 100 random graphs in order to calculate the Z-score. The Z-score list showed three top scoring results (excluding graphs with one or two vertices.)

\section{Conclusions and Future Work}
In this paper we have presented a newly developed motif detection tool called ProHash. As this tool is still in development, the algorithms provided and results presented are preliminary. there are many possible improvements for future work. 

design and test more alignment functions 
increase the max maotif size (currently 32)

\section{Work Distribution}
Work for this project was equally distributed between the two members. The following table breaks down the work distrubution for each fine-grained task based on the percentage of work each member was responsible for.

\begin{center}
\begin{table}
    \begin{tabular}{|l|l|l|}
        \hline
        \emph{Task}                         & \emph{Kirchgessner} & \emph{Pascoe} \\ \hline
        PPI Network Data             & 90\%           & 10\%     \\ \hline
        ProHash Algorithm            & 60\%           & 40\%     \\ \hline
        Feature Types/Hash Function  & 50\%           & 50\%     \\ \hline
        Graph/Overlay Generation     & 90\%           & 10\%     \\ \hline
        Hash Graph Generation
       & 40\%           & 60\%     \\ \hline
        Experiment with Kavosh       & 10\%           & 90\%     \\ \hline
        Hash Alignment Algorithm     & 10\%          & 90\%     \\ \hline
        Data Structure/Visualization & 90\%          & 10\%     \\ \hline
        Motif Query Set Generation   & 90\%          & 10\%      \\ \hline
        Z-Score Calculation          & 10\%          & 90\%      \\ \hline
        Experimentation              & 50\%           & 50\%     \\ \hline
        Result Comparison            & 50\%          & 50\%     \\ \hline
        Final Report                 & 50\%          & 50\%     \\
        \hline
    \end{tabular}
\end{table}
\end{center}

\section{Code Source}

source code for ProHash as well as dataset used in experimentation can be found at http://code.google.com/p/gator-ppi-motif/

\newpage 
\bibliography{report}
\bibliographystyle{IEEEtran}

\end{document}
